# -*- coding: utf-8 -*-

"""用分治的方法：
1）假设第 i 行有 f(i) 种合理的布局
2）那么第 i+1 行呢？迭代前面 i 行的结果，针对每个布局进行第 i+1 行的布局，筛选出第 i+1 行的布局

利用的数据结构：可以用一个长度为8的一维数组表示一种布局，数组下标表示行，每个位置的数值 [0: 8] 表示列"""

from copy import deepcopy

def check(layout, row, col):
    prerows = list(range(1, row))
    prerows.reverse()
    isok = True
    for pr in prerows:
        step = row-pr
        addr = layout[pr-1]
        if addr == col-step or addr == col or addr == col+step:
            isok = False
            break
    # print(layout, row, col, isok)
    return isok

def cal8queens():
    def go(row):
        if row == 1:
            layouts = []
            for col in range(1, 9):
                layout = [col,]
                layouts.append(layout)
            return layouts
        
        layouts = go(row-1)

        next_layouts = []

        for layout in layouts:
            for col in range(1, 9):
                if check(layout, row, col):
                    child_layout = deepcopy(layout)
                    child_layout.append(col)
                    next_layouts.append(child_layout)
        
        return next_layouts

    return go(8)

def pretty_print(layout):
    for col in layout:
        left = '--- ' * (col-1)
        right = '--- ' * (8-col)
        middle = '-x- '
        print(left+middle+right)

if __name__ == '__main__':
    layouts = cal8queens()
    for layout in layouts:
        print(layout)
        pretty_print(layout)

    print(len(layouts))
